package com.zwj.interview.动态规划;

/**
 * 输入一个只包含'0'和'1'的字符串，其中，'0'可以翻转成'1'，'1'可以翻转成'0'。请问至少需要翻转几个字符，
 * 才可以使翻转之后的字符串中所有的'0'位于'1'的前面？翻转之后的字符串可能只包含字符'0'或'1'。
 * 例如，输入字符串"00110"，至少需要翻转一个字符才能使所有的'0'位于'1'的前面。
 * 可以将最后一个字符'0'翻转成'1'，得到字符串"00111"
 */
public class 反转字符串NO {


    /**
     * 分析：
     * 如果一个只包含'0'和'1'的字符串S的长度为i+1，它的字符的下标范围为0～i。
     * 在翻转下标为i的字符时假设它的前i个字符都已经按照规则翻转完毕，所有的字符'0'都位于'1'的前面
     * <p>
     * 1、如果前i个字符在翻转某些'0'和'1'之后得到的符合要求的字符串的最后一个字符是'0'，
     * 那么无论下标为i的字符是'0'还是'1'，这i+1个字符组成的字符串都是符合要求的。
     *
     * 2、如果前i个字符在翻转某些'0'和'1'之后得到的符合要求的字符串的最后一个字符是'1'，
     * 那么必须保证下标为i的字符是'1'，这样才能确保这i+1个字符组成的字符串是符合要求的
     * <p>
     * <p>
     * 由于翻转下标为i的字符依赖于前i个字符翻转之后最后一个字符是'0'还是'1'，因此要分为两种情况讨论。
     * 假设函数f（i）表示把字符串中从下标为0的字符到下标为i的字符（记为S[0..i]，字符串中前i+1个字符组成的子字符串）
     * 变成符合要求的字符串并且最后一个字符是'0'所需要的最少翻转次数。
     * 假设函数g（i）表示把字符串中S[0..i]变成
     * 符合要求的字符串并且最后一个字符是'1'所需要的最少翻转次数。如果字符串的长度是n，
     * 那么f（n-1）和g（n-1）就是翻转整个字符串使字符串符合要求并且最后一个字符分别变成'0'和'1'的最少翻转次数，
     * 它们的最小值就是整个问题的解
     * <p>
     * 如果翻转之后下标为i的字符是'0'，那么下标为i-1的字符一定是'0'，否则就不满足所有的字符'0'位于'1'的前面的这个要求。
     * 当输入字符串中下标为i的字符（即S[i]）是'0'时，这一步不需要翻转，f（i）=f（i-1）；
     * 当输入字符串中下标为i的字符是'1'时，f（i）=f（i-1）+1，因为要把下标为i的字符翻转成'0'
     * <p>
     * 如果翻转之后下标为i的字符是'1'，那么无论下标为i-1的字符是'0'还是'1'都满足题目的要求。
     * 当输入字符串S[i]是'0'时，g（i）=min[f（i-1），g（i-1）]+1，因为要把第i个字符翻转成'1'；
     * 当S[i]是'1'时，此时不需要翻转字符，因此g（i）=min[f（i-1），g（i-1）]
     * <p>
     * 当i等于0时，f（0）和g（0）的值取决于下标为0的字符S[0]。如果S[0]为'0'，
     * 那么f（0）的值为0；如果S[0]为'1'，那么f（0）的值为1。g（0）则反之，如果S[0]为'0'，
     * 那么g（0）的值为1；如果S[0]为'1'，那么g（0）的值为0
     */

    public int minFlipsMonoIncr(String s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        int[][] dp = new int[2][2];
        char ch = s.charAt(0);
        //f(0)的值
        dp[0][0] = ch == '0' ? 0 : 1;
        //g(0)的值
        dp[1][0] = ch == '1' ? 0 : 1;

        /**
         * 定义了一个只有两行的二维数组dp，用来模拟一个表格，f（i）对应二维数组dp的第1行，g（i）对应dp的第2行。
         * 由于计算f（i）和g（i）只需要用到f（i-1）和g（i-1）的值，因此并不需要用一个长度为n的数组来保存f（i）和g（i）。
         * dp中每行的长度为2，f（i）和g（i）的值保存在对应行“i%2”的位置
         */
        for (int i = 1; i < len; i++) {
            ch = s.charAt(i);
            //计算f(i-1)
            int prev0 = dp[0][(i - 1) % 2];
            //计算g(i-1)
            int prev1 = dp[1][(i - 1) % 2];
            //计算f(i)的值
            dp[0][i % 2] = prev0 + (ch == '0' ? 0 : 1);
            //计算g(i)的值
            dp[1][i % 2] = Math.min(prev0, prev1) + (ch == '1' ? 0 : 1);
        }
        return Math.min(dp[0][(len - 1) % 2], dp[1][(len - 1) % 2]);

    }
}
